/**
 * @file maze_kabenobashi.js, an implementation for maze.js to generate a maze by Kabe-Nobashi method.
 *
 * @author nobu <nobu@ctmk.amanek.jp>
 */

(function(define) {
define([], function() {
	/**
	* @constructor
	*/
	var Maze_Algorithm = function() {
		// initialize
	};
	
	/**
	 * Generate a maze.
	 *
	 * @return {Maze.Result}
	 * @param {Maze.Config} config
	 * @throw {RangeError} It will throw if any config option is invalid.
	 */
	Maze_Algorithm.generate = function (config) {
		return generate_by_kabe_nobashi(config);
	};
	
	/**
	 * Signature of this method.
	 */
	Maze_Algorithm.Signature = function() {
		return "kabe-nobashi";
	};

	return Maze_Algorithm;

	/**
	 * @class
	 */
	function Work(config) {
		if (config.need_process) {
			this.process = [];
		}
		this.data = [];
	}
	
	/**
	 * Generate a maze by Kabe-Nobashi method.
	 * @return {Maze.Result}
	 * @param {Maze.Config} config
	 */
	function generate_by_kabe_nobashi(config) {
		validate(config);
		work = new Work(config);

		work.data = Maze_Algorithm.get_data_filled_with_edges(config.width, config.height, Maze_Algorithm.CellType.PATH, Maze_Algorithm.CellType.WALL);
		if (config.need_process) {
			work.process = Maze_Algorithm.get_process_filling_edges(config.width, config.height, Maze_Algorithm.CellType.WALL);
		}

		put_walls(work, config.width, config.height);
		
		result = new Maze_Algorithm.Result(config, Maze_Algorithm.Signature());
		if (config.need_data) {
			result.data = work.data;
		}
		if (config.need_process) {
			result.process = work.process;
			result.celltype_to_fill = Maze_Algorithm.CellType.PATH;
		}
		return result;
	}

	/**
	 * @param {Maze.Config} config
	 */
	function validate(config) {
		if ((config.width < 3) || (config.width%2 === 0) || (config.height < 3) || (config.height%2 === 0)) {
			// A limitation in this algorithm.
			throw new RangeError("config.width and config.height must be at least 3 and be a odd number.");
		}
	}

	/**
	 * Put walls next to the inner walls.
	 * @param {Maze_Algorithm.Work} work
	 * @param {number} x
	 * @param {number} y
	 */
	function put_walls(work, width, height) {
		var put_wall = ('process' in work) ? function (work, x, y) { return Maze_Algorithm.put_with_process(work, x, y, Maze_Algorithm.CellType.WALL); } : function (work, x, y) { return Maze_Algorithm.put_without_process(work, x, y, Maze_Algorithm.CellType.WALL); };
		
		var junktions = get_junctions_in_edges(width, height);
		
		var pos = get_next_start_point_randomly(junktions);
		while (pos) {
			var ds = get_shuffled_directions();
			for (var i = 0; i < ds.length; i += 1) {
				var d = get_h_v(ds[i]);
				if (is_path(work.data, pos.x+d.h*2, pos.y+d.v*2, width, height)) {
					put_wall(work, pos.x+d.h, pos.y+d.v);
					put_wall(work, pos.x+d.h*2, pos.y+d.v*2);
					pos.x = pos.x+d.h*2;
					pos.y = pos.y+d.v*2;
					junktions.push({ x: pos.x, y: pos.y });
					break;
				}
			}
			if (i === ds.length) {
				pos = get_next_start_point_randomly(junktions);
			}
		}
	}
	
	/**
	 * @param {Array.<Array.<Maze.CellType>>} data
	 * @param {number} x
	 * @param {number} x
	 * @param {number} width
	 * @param {number} height
	 */
	function is_path(data, x, y, width, height) {
		if (x < 0 || y < 0 || x >= width || y >= height) {
			return false;
		}
		return data[y][x] === Maze_Algorithm.CellType.PATH;
	}
	
	/**
	 * @return {Array.<number>}
	 */
	function get_shuffled_directions() {
		// shuffle by Fisher-Yates.
		return (function (arr) {
			var i, j, temp;
			arr = arr.slice();
			i = arr.length;
			if (i === 0) {
				return arr;
			}
			while (--i) {
				j = Math.floor(Math.random() * (i + 1));
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
			return arr;
		})([0, 1, 2, 3]);
	}

	/**
	 * @param {number} d - direction.
	 * @return {{h: number, v:number}}
	 */
	function get_h_v(d) {
		//    d:  v  h  dir
		// 0x00:  0  1   >
		// 0x01:  0 -1   <
		// 0x10:  1  0   v
		// 0x11: -1  0   ^
		h = (((d & 0x2) >> 1)-1) & (1 - ((d & 0x1) << 1));
		v = (((~d & 0x2) >> 1)-1) & (1 - ((d & 0x1) << 1));
		return { h: h, v: v };
	}
	
	/**
	 * @return {Array.<{ x: number, y: number }>}
	 */
	function get_junctions_in_edges(width ,height) {
		var junktions = [];
		(function() {
			var ys = [0, height-1];
			for (var i = 0; i < ys.length; i += 1) {
				var y = ys[i];
				for (var x = 2; x < width-1; x += 2) {
					junktions.push({ x: x, y: y });
				}
			}
		})();

		(function() {
			var xs = [0, width-1];
			for (var i = 0; i < xs.length; i += 1) {
				var x = xs[i];
				for (var y = 2; y < height-1; y += 2) {
					junktions.push({ x: x, y: y });
				}
			}
		})();
		return junktions;
	}
	
	/**
	 * @return {{ x: number, y: number }}
	 */
	function get_next_start_point_randomly(junktions) {
		if (junktions.length <= 0) {
			return null;
		}
		var n = Math.floor(Math.random()*junktions.length);
		var pos = junktions[n];
		junktions.splice(n, 1);
		return pos;
	}

});
})(typeof define !== 'undefined' ?
	// Use define for AMD if available
	define :
	// If no define, look for module to export as a CommonJS module.
	typeof module !== 'undefined' ?
	function(deps, factory) { module.exports = factory(); } :
	// If no define or module, attach to current context.
	typeof Maze !== 'undefined' ?
	function(deps, factory) { this.Maze.KabeNobashi = factory(); } :
	function(deps, factory) { this.Maze_KabeNobashi = factory(); }
);
